//-----------------------------------------------------------
//  Purpose:    Check pattern using a stack
//  Author:     John Gauch
//-----------------------------------------------------------
#include "stack3/stack3.h"
#include <cstdlib> 
#include <string>
using namespace std;

//-----------------------------------------------------------
// Check that pattern is of the form aaabbb
//-----------------------------------------------------------
bool check_pattern(string str)
{
   Stack stack;

   // Process the a's first
   unsigned int i = 0;
   while ((i < str.length()) && (str[i] == 'a'))
   {
      if (stack.IsFull()) return false;
      stack.Push('a');
      i++;
   }

   // Process the b's next
   while ((i < str.length()) && (str[i] == 'b'))
   {
      if (stack.IsEmpty()) return false;
      stack.Pop();
      i++;
   } 

   // Check if stack is empty and all input read
   return (stack.IsEmpty() && i == str.length());
}

//-----------------------------------------------------------
// Main program.
//-----------------------------------------------------------
int main()
{
   cout << "Enter pattern: ";
   string str;
   cin >> str;

   if (check_pattern(str))
      cout << "Pattern matches" << endl;
   else
      cout << "Pattern does NOT match" << endl;
   return 0;
}